package heap;
import java.util.*;
/**
 * 基于整型的最大堆实现
 * 此时根节点从0开始编号,若此时节点编号为k
 * 左子树的编号 = 2k + 1;
 * 右子树的编号 = 2k + 2;
 * 父节点的编号 = (k - 1) / 2
 * @author yuisama
 * @date 2022/02/28 19:51
 **/
public class MaxHeap {

    List<Integer>data;
    public MaxHeap()//无参构造方法的this调用
    {
        this(10);
    }
    public MaxHeap(int size)//初始化堆的大小
    {
        data=new ArrayList<>(size);
    }
    //将任意数组进行堆化操作
    public MaxHeap(int []arr)
    {//1先将arr数组的数据复制到data数组中
        data=new ArrayList<>(arr.length);
        for(int i:arr)
        {
            data.add(i);
        }
        //2从最后一个非叶子结点开始进行元素下沉构建
        for(int i=parent(data.size()-1);i>=0;i--)
        {
            siftDown(i);
        }
    }
    //向最大堆中添加一个新元素val
    public void add(int val)
    {
        //1直接在数组的尾部添加元素
        data.add(val);
        //2进行元素的上浮操作
        siftUp(data.size()-1);
    }

    //取出当前最大堆的最大值
    public int extractMax()
    {//判空操作
        if(isEmpty())
        {
            throw new NoSuchElementException("heap is empty!");
        }
        int max=data.get(0);//取出首个元素，即最大堆的根节点
        //1将数组末尾元素顶到堆顶(对于数组来说，首尾操作是最简单的)
        int lastVal=data.get(data.size()-1);
        data.set(0,lastVal);
        //2将末尾的元素进行删除
        data.remove((data.size()-1));
        //3进行元素的下沉操作
        siftDown(0);
        return max;
    }
    public  int peekMax()
    {
        if(isEmpty())
        {
            throw  new NoSuchElementException("heap is empty");
        }
        return data.get(0);
    }
    private  void siftDown(int k) {
        //还存在子树
        while (leftChild(k) < data.size()) {
            int j = leftChild(k);
            if (j + 1 < data.size() && data.get(j + 1) > data.get(j)) {
                //此时右子树存在且大于左子树的值
                j = j + 1;
            }
            //此时j就对应左右子树的最大值
            //和当前节点K去比较
            if (data.get(k) >=data.get(j)) {
                break;
            } else {
                swap(k, j);
                k = j;
            }
        }
    }
    //上浮操作
    private void siftUp(int k)
    {
        //上浮的终止条件：1该节点已经到达堆顶 2该节点小于父节点
        //循环迭代的条件：还存在父节点而且当前节点值>父节点
        while(k>0&&data.get(k)>data.get(parent(k))) {
            swap(k, parent(k));
            k = parent(k);
        }
    }
private void swap(int i,int j)//交换三连
{
    int temp=data.get(i);
    data.set(i,data.get(j));
    data.set(j,temp);
}
private boolean isEmpty()
{
    return data.size()==0;
}
private  int parent(int k)
{
    return (k-1)>>1;  //除二操作，确定父节点的索引
}
//根据索引得到左子树的索引
    private int leftChild(int k)
    {
        return (k<<1)+1;
    }
    private int rightChild(int k)
    {
        return (k<<1)+2;
    }
    @Override
    public  String toString()
    {
        return data.toString();
    }
}
